import java.util.ArrayList;
import java.util.HashMap;


public class KnapSackTest {
	
	private static HashMap<Integer, ArrayList<Double>> specialMatchTasks = new HashMap<Integer, ArrayList<Double>>();
	private static HashMap<Integer, Integer> addictionalMatchTasks = new HashMap<Integer, Integer>();
	private static int compsPerReduceTask;
	
	public static void main(String args[]) {
		
		/*
		int n = 10;
		int m = 2;
		int depth = -1;
		int profit[] = {0, 46, 50, 45, 58, 74, 52, 36, 30, 79, 61};
		int weight[] = {0, 81, 83, 43, 34, 68, 58, 60, 72, 42, 28};
		int capacity[] = {0, 125, 146};
		int sol[] = new int[n + 1];
		MultipleKnapSack.multipleKnapsack(n, m, profit, weight, capacity, depth, sol);
		if (sol[0] > 0) {
			System.out.println("Optimal solution found:");
			for (int i=1; i<=n; i++)
				System.out.print(" " + sol[i]);
				System.out.println("\n\nTotal profit = " + sol[0]);
			}
			else
				System.out.println("Error returned = " + sol[0]);
		*/
		
		//Parameters for test (Like Lars Publication)
		/*
		int n = 6; // Number of blocks
		int r = 4; // Number of reduce tasks 
		int depth = 0;
		int profit[] = {0, 1, 1, 1, 1, 1, 1}; // Could be used in the future to deal with data skewness.
		int weight[] = {0, 6, 1, 7, 1, 6, 7}; // Number of comparisons per block 
		int capacity[] = {0, 7, 7, 7, 7}; // Each with the number of comparisons of the largest block
		int sol[] = new int[n + 1];
		
		MultipleKnapSack.multipleKnapsack(n, r, profit, weight, capacity, depth, sol);
		if (sol[0] > 0) {
			System.out.println("Optimal solution found:");
			for (int i=1; i<=n; i++)
				System.out.print(" " + sol[i]);
			System.out.println("\n\nTotal profit = " + sol[0]);
		}
		else
			System.out.println("Error returned = " + sol[0]);
		*
		int r = 3;
		compsPerReduceTask = (int) Math.round(((7503/r) + 0.5));
		double comps = computeNumberComparisons(123);
		processMatchTask(1, comps);
		System.out.println(specialMatchTasks);
		System.out.println(addictionalMatchTasks);*/
		
		
		System.out.println(computeNumberSlicedComparisons(8, 1));
	}
	
	private static void processMatchTask(int k, double comps) {
		int slicePoint = slicePoint(compsPerReduceTask);
		// Slice point number comparisons 
		double spnc = computeNumberComparisons(slicePoint);
		generateSpecialMatchTasks(k, 123, comps, spnc);
	}

	private static void generateSpecialMatchTasks(int k, int blockSize, double comps, double spnc) {
		double compsRemains = comps - spnc;
		if (compsRemains > 0){
			int spAux = slicePoint((int)compsRemains) + 1;
			ArrayList<Double> residualsList = specialMatchTasks.get(k);
			if(residualsList == null) residualsList = new ArrayList<Double>();
			residualsList.add(blockSize - ((double)spAux));
			specialMatchTasks.put(k, residualsList);
			generateSpecialMatchTasks(k, spAux, computeNumberComparisons(spAux), spnc);
		}
		else{
			addictionalMatchTasks.put(k, blockSize);
		}
	}
	
	private static double computeNumberComparisons(int n){
		return (0.5)*n*(n-1);
	}
	
	public static int slicePoint(int c){
		return (int)(1+(Math.sqrt(4*2*c)))/2;
	}
	
	private static int computeNumberSlicedComparisons(int x, int y){
		return (int) (0.5*((2*x*y)-(y*y)-y));
	}
}
